Euclidean Algorithm Algorithm
The Euclidean Algorithm is an ancient mathematical method that offers an efficient way to find the greatest common divisor (GCD) of two numbers. Also known as the Euclid's Algorithm, it is named after the Greek mathematician Euclid, who first documented this method in his book Elements, around 300 BCE. The GCD, sometimes referred to as the highest common factor (HCF), is the largest positive integer that divides both numbers without leaving a remainder. The Euclidean Algorithm is widely applied in various fields, such as number theory, cryptography, and computer science, for its computational simplicity and effectiveness.
The fundamental principle behind the Euclidean Algorithm is based on the observation that the GCD of two numbers does not change if one of the numbers is replaced by their difference. The algorithm starts by dividing the larger number by the smaller number and then continually replacing the larger number with the remainder from the division until the remainder becomes zero. At this point, the smaller number is the GCD of the original two numbers. The Euclidean Algorithm can be implemented using either a recursive or an iterative approach, both of which are highly efficient in computing the GCD. This method has been adapted over time to work with polynomials and other mathematical structures, further expanding its utility in modern mathematics.
/*
Petar 'PetarV' Velickovic
Algorithm: Euclidean Algorithm
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
using namespace std;
typedef long long lld;
//Euklidov algoritam za racunanje najveceg zajednickog delioca (NZD) dva broja
//Slozenost: O(log^2 N)
int gcd(int a, int b)
{
if (a%b == 0) return b;
return gcd(b,a%b);
}
int main()
{
printf("%d\n",gcd(6,15));
return 0;
}
